1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuits. In particular, the present invention relates to the art of placing and connecting cells on integrated circuit chips.
2. Description of Related Art
An integrated circuit chip (hereafter referred to as an "IC" or a "chip") comprises cells and connections between the cells formed on a surface of a semiconductor substrate. The IC may include a large number of cells and require complex connections between the cells.
A cell is a group of one or more circuit elements such as transistors, capacitors, and other basic circuit elements grouped to perform a function. Each of the cells of an IC may have one or more pins, each of which, in turn, may be connected to one or more other pins of the IC by wires. The wires connecting the pins of the IC are also formed on the surface of the chip. For example, FIG. 1A shows a grossly simplified IC 10 having four cells 12, 14, 16, and 18 and ten pins 22, 24, 26, 28, 30, 22, 34, 36, 38, and 40. For simplicity, the cells will be denoted C.sub.nn and the pins will be denoted p.sub.nn where nn is the reference number of the cell or the pin used in the figure.
A net is a set of two or more pins which must be connected. Because a typical chip has thousands, tens of thousands, or hundreds of thousands of pins, which must be connected in various combinations, the chip also includes definitions of thousands, tens of thousands, or hundreds of thousands of nets, or sets of pins. The number of the nets for a chip is typically in the same order as the order of the number of cells on that chip. Commonly, a majority of the nets include only two pins to be connected; however, many nets comprise three or more pins. Some nets may include hundreds of pins to be connected. The IC 10 of FIG. 1A has two nets. The first net is a two-pin net comprising pins p.sub.34 and p.sub.40. The second net is a three pin net comprising pins p.sub.32, p.sub.36, and p.sub.38. A net can be denoted as a set of pins net (p.sub.1, p.sub.2, . . . p.sub.n)
A netlist is a list of nets for a chip.
Typically, an IC has a plurality of input pins and a plurality of output pins. The inputs are digital electrical signals being provided to the IC to be operated on. The outputs are digital electrical signals resulting from the operations of the IC. In between the input pins receiving the input signals to the IC and the output pins providing the output signals, the digital signals are operated on by a plurality of cells connected to each other. The connections of the cells are defined by the nets discussed hereinabove. The IC 10 of FIG. 1A has three input pins--p.sub.22, p.sub.24, and p.sub.26 --and two output pins--p.sub.28 and P.sub.30. For the purposes of describing the present invention, the pins of the IC which are neither input pins nor output pins will be referred to as intermediate pins.
One of the major constraints in design and fabrication of IC's is the time the IC requires to perform the specified function. This is often referred to as the performance of the IC. To determine the performance of an IC, various time measurements must to be considered. This is because, in addition to the input and output lines, the IC may include internal registers, or flip-flops, which may store certain output values and provide a portion of input values to the logic circuits. The performance of an IC may be defined as the period of time between the instant the last of the input signals are available to the logic circuit (whether the signals are from the input lines or from internal registers) to the instant the latest of the output signals are available from the logic circuit (whether the signals are for the output lines or for internal registers). The instant the input signal are applied is often denoted as t.sub.0. In any event, the performance of the IC is the period of time required for the logic circuits of the IC to performs its designed function irrespective of whether the inputs to the logic circuits are from the input pins or from the flip-flops or the outputs from the logic circuits are to the output pins or to the flip-flops. The performance of the IC is also referred to as the delay of the IC, or the IC delay.
For example, if the inputs to the IC 10 of FIG. 1A is applied at time t.sub.0 and the last of the output signals of the IC is available at t.sub.0 +3 ns (nano-seconds), then the delay of the IC 10 is 3 ns. This is true even if the other outputs signals of the IC are available at t.sub.0 +1 ns or at t.sub.0 +2 ns.
The performance of the IC depends on many factors such as the physical characteristics of the material, the layout of the cells, etc. Some of these factors, such as the physical characteristics of the material of the IC, cannot be changed during the cell placement and routing process. On the other hand, the placement of the cells and the routing of the nets can be modified during the placement process to improve the performance of the IC.
In order to increase the performance of the IC by modifying the placement of the cells and re-routing the nets, the paths of the IC must be analyzed and the critical paths identified. A path is an alternating sequence of nodes and edges connecting them. A critical path is the path or the paths among all possible paths of an IC which causes the highest delay of the IC.
An edge is the direction of signals flow through the cells and the wires. There are two types of edges in an IC. A cell edge is the direction of signals flow through the cells of an IC, and is obtained by "connecting" an input pin of a cell with an output pin of the same cell. If a cell takes an input signal at pin pi and produces and output signal at pin p.sub.o then the cell edge for that signal flow is denoted e.sub.c (p.sub.i, p.sub.o). Then, p.sub.i is called a parent of p.sub.o and p.sub.o a child of p.sub.i. For example, the IC 10 of FIG. 1A has several cell edges. The cell edges are e.sub.c (p.sub.22, p.sub.32), e.sub.c (p.sub.24, p.sub.34), e.sub.c (p.sub.26, p.sub.34), e.sub.c (p.sub.36, p.sub.38), e.sub.c (p.sub.38, p.sub.30), and e.sub.c (P.sub.40, p.sub.30) A pin may have none (for an input pin), one, or many parent(s), and none (for an output pin), one, or many children. If there is a path from node p.sub.1, to node p.sub.2, then p.sub.1 is an ancestor of p.sub.2 and p.sub.2 is a descendant of p.sub.1.
A net edge is the direction of signal flow from an output pin of a cell to an input pin of another cell, and is obtained by connecting the driver pin of a net with sink pin of the same net. A driver pin is the pin of a net which provides the signal to the sink pins of the same net and is typically an output pin of a cell. If a net has a driver pin P.sub.d which is connected to a sink pin p.sub.s, then the net edge for that signal flow is denoted e.sub.n (p.sub.d, p.sub.s). A sink pin is a pin of a net which receives the signal from a driver pin, and is often an input pin of a cell. For example, the IC 10 of FIG. 1A has several net edges. The net edges are e.sub.n (p.sub.32, p.sub.36), e.sub.n (p.sub.32, p.sub.38), and e.sub.n (p.sub.34, p.sub.40).
All edges of an IC are directed edges having a driver pin from which the signal originates and a sink pin to which the signal flows. For the purposes of the present invention, the distinction between the cell edges and net edges is not critical. Therefore, an edge will mean a cell edge or a net edge, and will be denoted .sub.e (p.sub.p, p.sub.c) to indicate an edge between a parent pin p.sub.p and a child pin p.sub.c.
A path may be denoted as a set of pins and edges, for example, path(p.sub.1, e(p.sub.1, p.sub.2), p.sub.2, e(p.sub.2, p.sub.3), p.sub.3, . . . ). An alterative expression of the path is to merely list the nodes, for example, path(p.sub.1, p.sub.2, . . . ). Regardless of how it is denoted, a path comprises pins and edges connecting the pins.
The relationships of ancestor and descendent may exist between an edge and a node or between two edges. For example, if p.sub.1, is an ancestor of p.sub.2, then p.sub.1 is also an ancestor of the edge e(p.sub.2, p.sub.3). Similarly, if p.sub.7 is a descendent of p.sub.4, then e(p.sub.7, p.sub.8) is a descendent of p.sub.4.
FIG. 1B illustrates a directed graph constructed from the pins and the edges of the IC 10 of FIG. 1A. Each node of the graph 50 correspond to a pin of the IC 10 of FIG. 1, and each edge of the graph 50 correspond to an edge of the same IC 10. In FIG. 1B, the edges are directed. That is, each of the edges is indicated by an arrow to show the direction of the signal flow. In the present specification, the terms pins and the nodes will be used interchangeably unless otherwise specified.
Because each of the edges of the directed graph 50 of FIG. 1B represents a signal travel through a cell or through a wire, each of the edges can be assigned an edge delay to indicate the time required for a signal to travel from the parent pin to the child pin. Then, the directed graph is referred to as a directed timing graph or merely a timing graph. The delay of e(p.sub.1, p.sub.2) is denoted delay(p.sub.1, p.sub.2). It takes time for electrical signal to travel from pin to pin; thus, every edge has a delay.
The paths of the timing graph of an IC can be analyzed to locate the critical paths.
The timing characteristics of the cell edges can be obtained from libraries. However, the timing characteristics of net edges are not easily obtainable before the actual routing of the nets.
The period of time required for signals to travel from an input pin to pin p may be called the arrival time of pin p. The arrival time of node p, denoted arrival(p), is the latest time a signal from an input mode reaches node though any available path from an input node to the node. Formally, arrival(p) is ##EQU1##
To determine the performance, or the delay, of an IC, each of the paths of the IC must be analyzed. The IC delay may be expressed as the largest arrival time of any of the output nodes, or ##EQU2##
As discussed above, the IC delay is the period of time signals take to travel from an input pin to an output pin. Accordingly, it is not possible to determine the IC delay at an output pin without first determining the delay from the input pins to each of the intermediate pins the signal travels through to arrive at the output pin. In fact, for any pin not an input pin, arrival(p) cannot be determined unless the arrival(p) of all of its ancestors are first found.
For example, referring to FIG. 2, the IC delay of the chip represented by the timing graph 70 cannot be determined unless arrival(p.sub.90) and arrival(p.sub.92) are found. However, arrival(p.sub.92) cannot be found until arrival(p.sub.86) is first determined. Likewise, arrival(p.sub.86) cannot be found until arrival(p.sub.82) and arrival(.sub.80) are found, and so on.
To find the delay of an IC, the arrival time of each of the pins of the IC must be determined. Because a typical IC contains many thousands or even millions of pins and paths, the analysis of arrival times for each of the pins are computationally expensive. Accordingly, the IC delay analysis of large IC circuits requires a large amount of time even when utilizing very powerful computers.
Additionally, IC's usually contain paths the delay of which should not be considered in the determination of the IC delay. These paths are called false paths. For example, self-test circuits of the IC may cause high IC delay. However, the self-test circuits are not used during the ultimate use of the IC, and the IC delay, as defined by the self-test, would be misleading. For instance, if the self-test circuits causes the IC to have the IC delay of 20 ns where the other, more relevant portions of the IC has the delay of 5 ns, then the IC delay of 20 ns is misleading.
In short, to determine the delay of an IC, only the true paths of the IC should be considered. Calculation of the arrival times and the delays of the false paths wastes the processing time and provides misleading results for the IC.